package com.jack.leetcode.eachproblem_2020;

public class 重构字符串 {

    public String reorganizeString(String S) {
        int[] count = new int[26];
        int n = S.length();
        int max = 0;
        for(char c : S.toCharArray()){
            count[c - 'a']++;
            max = Math.max(count[c - 'a'], max);
        }
        if(max > (n + 1) / 2){
            return "";
        }
        int halfLength = n / 2;
        int evenIndex = 0, oddIndex = 1;
        char[] rebuildString = new char[n];
        for(int i = 0;i < 26;i++){
            char c = (char)('a' + i);
            while(count[i] > 0 && count[i] <= halfLength && oddIndex < n){
                rebuildString[oddIndex] = c;
                oddIndex += 2;
                count[i]--;
            }
            while(count[i] > 0){
                rebuildString[evenIndex] = c;
                evenIndex += 2;
                count[i]--;
            }
        }
        return new String(rebuildString);
    }
}
